import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 不允许修改 链表。
 * User: 86189
 * Date: 2022-02-13
 * Time: 19:53
 */
class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //哈希表法，遇到重复的节点，说明就是找到了入环口
//        Set<ListNode> set=new HashSet<>();
//        ListNode cur=head;
//        while(cur!=null){
//            if(!set.contains(cur)){
//                set.add(cur);
//            }else{
//                return cur;
//            }
//            cur=cur.next;
//        }
//        return null;

        //双指针法，定义一个快指针和慢指针，首先判断有没有环，怎么判断呢？
        //让快指针走两步，慢指针走一步，这样是为了跟容易相遇，能相遇说明有环，那么怎么找到这个环入口呢？
        //是这样的，相遇之后让快指针回到头指针的位置，慢指针还是在相遇的位置开始走，一人走一步，直到他们相遇了，就找到了环入口
        //那么为什么要这样走呢？
        //我们可以通过数学公式和画图去证明，假设从头节点到环入口的节点数为x,环内的节点数为c，相遇点到环入口的节点数为y,
        //首先假设一种普通情况，假设快指针在环内走了一圈多就遇到了慢指针，也就是这样的：
        //慢指针走了：x+c-y         快指针就走了：x+c+c-y    假设这样他们就相遇了，我们是要知道头结点到入口节点的距离也就是x
        //经过化简，由于快指针走的路程是慢指针的两倍，所以2(x+c-y)=x+c+c-y,化简得，在普通情况下，x=y,
        // 也就是说，从头结点到环入口的距离跟相遇点到环入口的距离是一样的
        //那么我们就可以让一个指针从头结点，一个指针从相遇点，两个同时走，一人一步，这样他们就肯定会相遇在环入口

        //那么对于特殊情况，也就是环太小了，然而头结点到环入口的距离太长了，导致fast在环内走了很多圈才与slow相遇
        //那么慢指针走了：x+c-y    快指针走了：x+nc+c-y
        //也就是2(x+c-y)=x+nc+c-y   ---->   x=(n-1)c+y
        //那么也就可以把(n-1)c+y看成是一条以相遇点为起点的这么一段距离的直线，跟一条长度为x的直线，两条直线一个从头节点出发
        //一个从相遇节点出发，经过一人一步，他们长度相等，最终会到达同一个终点就是环入口

        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            //先判断有无环，方法是快的走两步，慢的走一步，能相遇就是由环
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                //有环，接下来要找入环口
                fast=head;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                //相遇了就找到了入环口
                return slow;
            }
            //对于不相等的情况，肯定就是没有环，最终fast会等于null
        }
        return null;
    }
}
